一种基于数据空间自适应规则网格划分的Skd-tree最近邻算法

摘要

针对现有kd-tree KNN算法的不足,提出了一种基于规则数据空间网格划分的Skdtree KNN算法。该树形结构把数据置于空间网格内部,能更好地利用数据的空间分布特性,可以在更小的范围内对被查询数据定位,有效避免对部分无关数据的计算或回溯;同时,为了适应网格空间的规则性,算法中采用了超方体而非超球体来查询局域空间中的最优结果,避免了空间异构带来的缺点。数字实验的结果证明:Skd-tree KNN比kd-tree KNN具备更好的索引定位精度、更少的无关数据回溯和计算、更短的查询时间,尤其适用于数据样本较大或高维度数据的最近邻查询。